\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{natbib}

%opening
\title{Multi-agent Learning Seminar\\An Architecture for Action Selection in Robotic Soccer}
\author{Daniel Silva, Nguyen Cu and Joseph Chege}

\begin{document}

\maketitle

\section{Introduction}

In \citep{stone2001architecture}, the authors describe key elements in \textbf{ATT-CMUnited-2000} strategy. Namely:

\begin{enumerate}
  \item Option evaluation architecture: all actions (passing, dribbling, kicking, etc) can be scored and compared among each other;
  \item Leading passes (LP): pass the ball at an oblique angle of the intended receiver, not passing only directly;
  \item Efficient numerical algorithm: leading passes incurs much more calculations, which need to be done as fast as possible;
  \item Force fields (FF): to control the position of players without the ball.
\end{enumerate}

The goal of this work is to incorporate \emph{Leading passes} and \emph{Force fields} in WrightEagle's RoboCup client \citep{bai2010wrighteagle} and measure the influence on its performance.

\section{Implementation}

Like in \citep{stone2001architecture}, WrightEagle uses an \emph{Option evaluation architecture}, different actions in nature are planned, scored and compared against each other, the highest score determines what the player will do. Options are called \emph{Behaviors}. There are four main behaviors:

\begin{itemize}
  \item \emph{BehaviorPenaltyPlanner}
  \item \emph{BehaviorSetplayPlanner}
  \item \emph{BehaviorAttackPlanner}
  \item \emph{BehaviorDefensePlanner}
\end{itemize}

Each behavior may be composed of other behaviors. \emph{BehaviorAttackPlanner} is compromised of \emph{BehaviorInterceptPlanner}, \emph{BehaviorShootPlanner}, \emph{BehaviorPassPlanner}, \emph{BehaviorDribblePlanner}, \emph{BehaviorPositionPlanner} and \emph{BehaviorHoldPlanner}. \emph{BehaviorDefensePlanner} on the other hand, is made of \emph{BehaviorFormationPlanner}, \emph{BehaviorBlockPlanner} and \emph{BehaviorMarkPlanner}.

\subsection{Leading passes}

WrightEagle only consider direct passes, that is, passing directly to your teammate. We altered \emph{BehaviorPass.cpp} to take into account nearby opponents, and slightly change the angle of the pass, by adding the following:

\begin{verbatim}
int position_predicted_scale=2;
Vector root_target = pass.mTarget;
Vector teamate_predict_pos = 
  mWorldState.GetTeammate(tm2ball[i]).GetPredictedPos(position_predicted_scale);
Vector rel_opp_pos = mWorldState.GetOpponent(opp2tm[index_closed_opponent]).GetPos();
Vector V1= rel_opp_pos-root_target;
Vector V2 = teamate_predict_pos -root_target; 
double reduce_rate = V2.Mod() /V1.Mod();
reduce_rate = pow(reduce_rate,2);
pass.mTarget= root_target+ (teamate_predict_pos - rel_opp_pos)*reduce_rate;
\end{verbatim}

Figure \ref{fig:pass} illustrates what is happening.

\begin{figure}[ht!]
 \centering
 \includegraphics[width=0.7\textwidth]{pass2.png}
 \caption{Passing with an opponent nearby.}
 \label{fig:pass}
\end{figure}

The closest opponent influences pass direction, but only slightly, teammate positioning is still the largest factor and its velocity is important also. Keep in mind that, teammate has a reason to move with current velocity, because of formation tactic and positioning strategy, therefore passing should be done to the expected position of the teammate.  Besides, influence by closest opponent is reversed by distance to teammate, that means if the opponent is far enough passing position is effected only by the position and velocity of the teammate.

\subsection{Force fields}

As described in \citep{stone2001architecture} force fields are divided into two categories:

\begin{itemize}
  \item Strategic: applies to players far from the ball;
  \begin{itemize}
    \item $B$: bounds-repellent, strong when players are within 5 meters of the edge of the field;
    \item $O$: offside-repellent, causes player to retreat if the opponent's offside line is within 5 meters;
    \item $S$: inter-player force, attractive when players are slightly more than 20 meters apart and repulsive if they are closer.
  \end{itemize}
  \item Tactical: applies to players near the ball;
  \begin{itemize}
    \item  $T$: repulsive force between offensive players, strong when the ball is within 8 meters;
    \item  $C$: repulsive force between players and opponents, also called get clear, its strength is proportional to the likehood that the pass will be intercepted by a defender.
  \end{itemize}
\end{itemize}

We altered \emph{BehaviorPosition.cpp} and \emph{BehaviorFormation.cpp} by adding functions: \emph{softIf}, \emph{softEq}, \emph{dist}, \emph{forceFieldB}, \emph{forceFieldO}, \emph{forceFieldS}, \emph{forceFieldT} and \emph{forceFieldC}.

\section{Results}

We compare results using the following attributes: score, ball possession and successful passes. Score is simply number of goals from each side in the match, ball possession and successful passes are much harder to compute. In this case a team has possession of the ball if a member of the team is the closest player to the ball, and the closest opponent to that player is at least 1 meter away. A successful pass, consists in executing a pass and having possession of the ball at least 10 time units afterwards (otherwise you are dribbling) and at most 15 time units (otherwise you recovered a ball that was intercepted).

To gather the required information we altered \emph{BehaviorPenaltyPlanner}, since it is the first behavior every player plans, by adding the following:

\begin{verbatim}
Vector self=mSelfState.GetPos();
Vector opponent=mWorldState.GetOpponent(mPositionInfo.GetClosestOpponentToBall()).GetPos();
Vector ball=mBallState.GetPos();
double diBallSelf=sqrt(pow(ball.X()-self.X(), 2.0)+pow(ball.Y()-self.Y(), 2.0));
double diBallOpponent=sqrt(pow(ball.X()-opponent.X(), 2.0)+pow(ball.Y()-opponent.Y(), 2.0));
double diSelfOpponent=sqrt(pow(self.X()-opponent.X(), 2.0)+pow(self.Y()-opponent.Y(), 2.0));
std::cout<<"dgk possession "<<mWorldState.CurrentTime()<<" "<<mSelfState.GetUnum()
  <<" "<<diBallSelf<<" "<<diBallOpponent<<" "<<diSelfOpponent<<std::endl;
\end{verbatim}

A total of 30 games were played. 10 control games where two WrightEagle clients played against each other without any of our modifications, 10 with LP only and 10 with LP and FF control. Ball possession and successful passes are calculated for the team with the result on the left, which is also the team that contains our modifications in Tables \ref{tab:passOnly} and \ref{tab:passFF}. Results are displayed below:

\begin{table}[!ht]
  \centering
  \begin{tabular}{|c|c|c|c|}
    \hline
    Game & Score & Ball possession & Successful passes \\ \hline
    1 & 4 - 5 & 41\% & 71\% \\ \hline
    2 & 3 - 1 & 47\% & 77\% \\ \hline
    3 & 1 - 0 & 41\% & 73\% \\ \hline
    4 & 7 - 5 & 46\% & 78\% \\ \hline
    5 & 5 - 6 & 41\% & 77\% \\ \hline
    6 & 3 - 5 & 43\% & 67\% \\ \hline
    7 & 4 - 2 & 42\% & 79\% \\ \hline
    8 & 5 - 6 & 41\% & 70\% \\ \hline
    9 & 5 - 4 & 42\% & 79\% \\ \hline
    10 & 1 - 4 & 38\% & 71\% \\ \hline
  \end{tabular}
  \caption{Unmodified clients results.}
  \label{tab:control}
\end{table}

\begin{table}[!ht]
  \centering
  \begin{tabular}{|c|c|c|c|}
    \hline
    Game & Score & Ball possession & Successful passes \\ \hline
    1 & 1 - 3 & 40\% & 70\% \\ \hline
    2 & 3 - 2 & 38\% & 70\% \\ \hline
    3 & 3 - 7 & 37\% & 69\% \\ \hline
    4 & 6 - 3 & 41\% & 78\% \\ \hline
    5 & 7 - 6 & 42\% & 72\% \\ \hline
    6 & 8 - 5 & 36\% & 70\% \\ \hline
    7 & 0 - 1 & 36\% & 66\% \\ \hline
    8 & 3 - 5 & 39\% & 75\% \\ \hline
    9 & 7 - 3 & 39\% & 75\% \\ \hline
    10 & 5 - 8 & 36\% & 79\% \\ \hline
  \end{tabular}
  \caption{Leading passes only results.}
  \label{tab:passOnly}
\end{table}

\begin{table}[!ht]
  \centering
  \begin{tabular}{|c|c|c|c|}
    \hline
    Game & Score & Ball possession & Successful passes \\ \hline
    1 & 1-5 & 44\% & 73\% \\ \hline
    2 & 0-2 & 41\% & 74\% \\ \hline
    3 & 2-4 & 40\% & 70\% \\ \hline
    4 & 0-2 & 40\% & 73\% \\ \hline
    5 & 4-4 & 43\% & 71\% \\ \hline
    6 & 1-1 & 42\% & 77\% \\ \hline
    7 & 4-3 & 41\% & 71\% \\ \hline
    8 & 1-3 & 39\% & 70\% \\ \hline
    9 & 1-4 & 42\% & 65\% \\ \hline
    10 & 2-2 & 47\% & 74\% \\ \hline
  \end{tabular}
  \caption{Leading passes and force fields control results.}
  \label{tab:passFF}
\end{table}

\newpage

Applying the paired \emph{t-test} yields the following \emph{p-values}:

\begin{table}[!ht]
  \centering
  \begin{tabular}{|c|c|c|c|}
    \hline
    Feature & Control vs. LP & Control vs. LP and FF \\ \hline
    Score & 1.00 & 0.08 \\ \hline
    Ball possession & 0.00 & 0.79 \\ \hline
    Successful passes & 0.36 & 0.18 \\ \hline
  \end{tabular}
  \caption{\emph{p-values}.}
\end{table}

Only using LP didn't change the number of wins or the number of successful passes, but it changed ball possession, unfortunately for the worse. When using FF the null hypothesis can be rejected regarding score, but performance is consistently worse, almost all games were lost.

\section{Conclusion}

The modifications suggested in the article are too shallow for WrightEagle. Passing and positioning are optimized, given its complex architecture, that allows for comparison of different actions in nature, and several possible behaviors, for instance \emph{BehaviorSetplayPlanner} which is probably responsible for the majority of goals. During the testing phase, we noticed that the majority of goals happen when a pass is made from the corner of the opponent's goal, to a teammate in the center, that just kicks the ball forward, FF doesn't help at all, since field $B$ and $O$ are probably pushing the receiver back to its team field.

\bibliographystyle{plainnat}
\bibliography{biblio}

\end{document}
